package hot_100;

import kotlin.Pair;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class 腐烂的橘子 {
    public static void main(String[] args) {

    }

    int[][] fang = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int cnt = 0, n, m;

    public int orangesRotting(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        Deque<int[]> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != 0) {
                    if (grid[i][j] == 2) {
                        deque.addFirst(new int[]{i, j});
                        continue;
                    }
                    cnt++;
                }
            }
        }
        int time = -1;
        while (!deque.isEmpty()) {
            time++;
            int h = deque.size();
            for (int i = 0; i < h; i++) {
                int[] temp = deque.pollLast();
                for (int[] ints : fang) {
                    int dx = temp[0] + ints[0];
                    int dy = temp[1] + ints[1];
                    if (dx >= 0 && dx < n && dy >= 0 && dy < m && grid[dx][dy] == 1) {
                        grid[dx][dy] = 2;
                        cnt--;
                        deque.addFirst(new int[]{dx, dy});
                    }
                }
            }
        }
        if (time <= 0)
            return time;
        if (cnt != 0)
            return -1;
        return time;
    }
}
